[NOI1999][POJ1190]生日蛋糕

发表于 | 分类于 ， ， ， | | 阅读次数:

Description

7月17日是Mr.W的生日，ACM-THU为此要制作一个体积为Nπ的M层生日蛋糕，每层都是一个圆柱体。
设从下往上数第i(1 <= i <= M)层蛋糕是半径为Ri, 高度为Hi的圆柱。当i < M时，要求Ri > Ri+1且Hi > Hi+1。
由于要在蛋糕上抹奶油，为尽可能节约经费，我们希望蛋糕外表面（最下一层的下底面除外）的面积Q最小。
令Q = Sπ
请编程对给出的N和M，找出蛋糕的制作方案（适当的Ri和Hi的值），使S最小。
（除Q外，以上所有数据皆为正整数）

Input

有两行，第一行为N（N <= 10000），表示待制作的蛋糕的体积为Nπ；第二行为M(1<=M <= 20)，表示蛋糕的层数为M。

Output

仅一行，是一个正整数S（若无解则S = 0）。

Sample Input

1
2
100
2

Sample Output

1
68

Hint

圆柱公式
体积$V = πR^2H$
侧面积$A’ = 2πRH$
底面积$A = πR^2$

题解

对于这种没有多项式复杂度的题目显然最好的做法是搜索。
但是这可是道NOI的题目，所以我们还要进行一些剪枝，我这里可能不是所有的剪枝都用了，但足够了，POJ16ms

首先我们搜索有5个状态，剩余层数，用了的表面积，用了的体积，当前层的高度，当前层的半径。

剪枝

  1. 上下界剪枝（范围剪枝）
    我们在第dep层时，只需要在以下范围内枚举高度和半径即可：
    $R\in [dep,min(\lfloor \sqrt{N-v} \rfloor,r[dep+1]-1)]$
    $H\in [dep,min(\lfloor \frac{N-v}{R^2} \rfloor,h[dep+1]-1)]$
  2. 优化搜索顺序
    上面的范围中，倒序枚举。
  3. 可行性剪枝/最优化剪枝（见注释）

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
#include<iostream>
#include<cstdio>
#include<cmath>
using namespace std;
int n,m,ans;
int mincake[30];

void dfs(int last,int s,int v,int h,int r){
	if(last==0){
		if(v==n&&s<ans){
			ans=s;
		}
		return;
	}
	if(v+mincake[last-1]>n)return;//当前体积+下一层最小体积>总体积，可行性剪枝
	if(2*(n-v)/r+s>=ans)return;//最优性剪枝
	for(int i=r-1;i>=last;i--){
		if(last==m)s=i*i;
		int hh=min((n-v-mincake[last-1])/(i*i),h-1);
		for(int j=hh;j>=last;j--){
			dfs(last-1,s+2*i*j,v+i*i*j,j,i);
		}
	}
}

int main(){
	cin>>n>>m;
	ans=1<<30;
	for(int i=1;i<=20;i++)mincake[i]=mincake[i-1]+i*i*i;//第i层最小的蛋糕体积
	dfs(m,0,0,n+1,n+1);
	if(ans==1<<30)cout<<0;
	else cout<<ans;
	return 0;
}